package com.bigshen.algorithm.fSort.solution01BubbleInsertSelect;

public class Sort {

    /**
     * 冒泡排序，依次将最大值冒泡冒泡放至队尾
     * 比较相邻另个位置，不是顺序的1换
     * @param array
     */
    public void bubbleSort(int[] array) {

        if (null == array || array.length < 2) {
            return;
        }

        for (int i = 1; i < array.length; i++) {

            for (int j = 0; j < array.length-i; j++) {

                if (array[j] > array[j+1]) {
                    // 前面的大，前后替换
                    int tmp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = tmp;
                }

            }
//            print(array);
        }

    }

    /**
     * 插入排序
     * 第一层for循环，定位插入节点 insertNode
     *   第二层while循环， 循环判断 insertNode 和之前一系列节点相比，判断插入的位置
     *
     * @param array
     */
    public void insertSort(int[] array) {

        if (null == array || array.length < 2) {
            return;
        }

        for (int i = 1; i < array.length; i ++) {

            int insertNode = array[i];
            int j = i;
            while (j > 0 && insertNode < array[j-1]) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = insertNode;
            print(array);
        }

    }

    /**
     * 选择排序，找出最小放至队头
     * @param array
     */
    public void selectSort(int[] array) {

        if (null == array || array.length < 2) {
            return;
        }

        for (int i = 0; i < array.length; i++){

            int min = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }

            if (i != min) {
                // 找到最小值，互换位置
                int tmp = array[i];
                array[i] = array[min];
                array[min] = tmp;
            }

//            print(array);

        }

    }

    public static void main(String[] args) {

//        int[] array = {8,6,9,7,3,4,1};

        int[] array = new int[10];


        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random()*10000);
        }
        // 冒泡
//        long start1 = System.currentTimeMillis();
//        new Sort().bubbleSort(array);
//        long end1 = System.currentTimeMillis();
//        System.out.println("BubbleSort : " + (end1-start1));



        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random()*10000);
        }
        // 插入
        long start2 = System.currentTimeMillis();
        new Sort().insertSort(array);
        long end2 = System.currentTimeMillis();
        System.out.println("InsertSort : " + (end2-start2));


        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random()*10000);
        }
        // 选择
//        long start3 = System.currentTimeMillis();
//        new Sort().selectSort(array);
//        long end3 = System.currentTimeMillis();
//        System.out.println("SelectSort : " + (end3-start3));


    }

    private void print(int[] array) {

        System.out.println();
        for (int element : array) {
            System.out.print(element + ",");
        }

    }


}
